package com.south.base.test.arithmetic;

import com.south.base.test.arithmetic.tree.BinaryTree;
import com.south.base.test.arithmetic.tree.TreeNode;
import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2020/8/5 9:22
 */
public class Rob {
    private BinaryTree binaryTree = new BinaryTree();

    /**
     * 打家劫舍 III
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
     * 这个地区只有一个入口，我们称之为“根”。
     * 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。
     * 一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
     * 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     * 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
     */
    @Test
    public void rob() {
        Assert.assertEquals(7, rob(binaryTree.deserialize("3,2,,3,,,3,,1,,")));
        Assert.assertEquals(9, rob(binaryTree.deserialize("3,4,1,,,3,,,5,,1,,")));
        Assert.assertEquals(10, rob(binaryTree.deserialize("3,4,2,,,3,,,5,,1,,")));

        Assert.assertEquals(3, rob(new int[]{2, 3, 2}));
        Assert.assertEquals(4, rob(new int[]{1, 2, 3, 1}));
        Assert.assertEquals(3, rob(new int[]{1, 1, 1, 2}));
    }

    public int rob(TreeNode root) {
        int[] rootStatus = robDfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }

    public int[] robDfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] l = robDfs(node.left);
        int[] r = robDfs(node.right);
        int selected = node.val + l[1] + r[1];
        int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{selected, notSelected};
    }

    /**
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
     * 这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
     */
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int pre = 0, cur = nums[0], tmp;
        int pre2 = 0, cur2 = 0, tmp2;
        for (int i = 1; i < nums.length - 1; i++) {
            int num = nums[i];
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
            tmp2 = cur2;
            cur2 = Math.max(pre2 + num, cur2);
            pre2 = tmp2;
        }
        cur2 = Math.max(pre2 + nums[nums.length - 1], cur2);
        return Math.max(cur, cur2);
    }

}
